package F.树;

import java.util.LinkedList;
import java.util.Queue;

public class _剑指Offer55_I_二叉树的深度 {
    /**
     * 自解：层次遍历 速度过慢
     * @param root
     * @return
     */
    public int maxDepth(TreeNode root) {

        Queue<TreeNode> queue = new LinkedList<>();
        if (root == null){
            return 0;
        }
        int level = 0;
        queue.add(root);
        while (!queue.isEmpty()){
            int size = queue.size();
            while (size>0){
                root = queue.poll();
                if (root.left != null){
                    queue.add(root.left);
                }
                if (root.right != null){
                    queue.add(root.right);
                }
                size--;
            }

            level++;

        }

        return level;

    }

    /**
     * 自解：递归法
     * root的深度 是左子树和右子数最大的深度加1
     * ---贼快
     */
    public int maxDepth1(TreeNode root) {
        if (root == null){
            return 0;
        }

        return Math.max(maxDepth1(root.right),maxDepth1(root.left))+1;
    }
}
